11137 - Ingenuous Cubrency/11137.cpp

   1 /*
   2   11137 - Ingenuous Cubrency [UVa Online Judge]
   3   Andrés Mejía-Posada [http://blogaritmo.factorcomun.org]
   4
   5   Programación dinámica, coin change
   6
   7   Aceptado por el juez.
   8  */
   9 #include <iostream>
  10
  11 using namespace std;
  12
  13 const int COINS = 21, MONEY = 9999;
  14
  15 int coins[COINS];
  16
  17 /*
  18   dp[i][j] = Utilizando las primeras i monedas, de cuantas maneras puedo fomar exactamente j cubos?
  19  */
  20 unsigned long long dp[COINS][MONEY+1];
  21
  22 int main(){
  23   for (int i=1; i<=COINS; ++i){
  24     coins[i-1] = i*i*i;
  25   }
  26
  27   for (int i=0; i<COINS; ++i){
  28     dp[i][0] = 1ULL; //Cero cubos los puedo formar de una única manera: coger ninguna moneda.
  29     for (int j=1; j<=MONEY; ++j){
  30       dp[i][j] = 0ULL;
  31       if (i > 0) dp[i][j] += dp[i-1][j];
  32       if (j - coins[i] >= 0) dp[i][j] += dp[i][j - coins[i]];
  33     }
  34   }
  35
  36   int n;
  37   while (cin >> n) cout << dp[COINS-1][n] << endl;
  38
  39
  40   return 0;
  41 }